package exercise;

// https://leetcode.cn/problems/find-the-duplicate-number/
public class L230703_II {
    public int findDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length-1;

        while (left < right) {
            int mid = (right - left) / 2 + left;
            int count = 0;

            for (int x : nums) {
                if (x <= mid) {
                    count ++;
                }
            }

            if (count > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
